Multi-carrier modulation supports wideband wireless communication with a guaranteed quality of service (QoS). Instead of employing a very complicated adaptive equalizer to reduce intersymbol interference (ISI), multi-carrier modulation satisfies a stringent service requirement by partitioning a single wideband channel into many subchannels that are free of ISI, Bingham et al., “Multi-carrier modulation for data transmission: An idea whose time has come,” IEEE Commun. Mag., vol. 28, no. 5, pp. 5-14, May 1990, Linnartz et al., “Multi-carrier CDMA in indoor wireless radio networks,” Proc. IEEE PIMRC, September 1993, pp. 109-113, and Hara et al., “Overview of multi-carrier CDMA,” IEEE Commun. Mag., vol. 35, no. 12, pp. 126-133, December 1997.
Although multi-carrier modulation simplifies the design of equalizers, it causes a set of resource allocation problems. To achieve efficient utilization of scarce radio resources such as bandwidth, power, and transmission time, an optimal resource allocation strategy is desired.
It is well known that a water-filling power allocation is an optimal solution to achieve the capacity of a set of parallel channels. Throughput capacity and optimal resource allocation are described by Tse et al., “Multiaccess fading channels—Part I: Polymatroid structure, optimal resource allocation and throughput capacities,” IEEE Trans. Inf. Theory, vol. 44, no. 7, pp. 2796-2815, November 1998.
In single-user multi-carrier networks, one well-known water-filling method is the Hughes-Hartogs algorithm, see. Hughes-Hartogs, “Ensemble modem structure for imperfect transmission media,” U.S. Pat. No. 4,679,227, Jul. 7, 1987, Hughes-Hartogs, “Ensemble modem structure for imperfect transmission media,” U.S. Pat. No. 4,731,816, Mar. 15, 1988, and Hughes-Hartogs, “Ensemble modern structure for imperfect transmission media,” U.S. Pat. No. 4,833,706, May 30, 1989.
A number of efficient resource allocation methods are known, aee P. S. Chow, J. M. Cioffi, and J. A. C. Bingham, “A practical discrete multitone transceiver loading algorithm for data transmission over spectrally shaped channels,” IEEE Trans. Commun., vol. 43, no. 2/3/4, pp. 773-775, February/March/April 1995; I. Kalet, “The multitone channel,” IEEE Trans. Commun., vol. 37, no. 2, pp. 119-124, February 1989; T. J. Willink and P. H. Wittke, “Optimization and performance evaluation of multi-carrier transmission,” IEEE Trans. Inf. Theory, vol. 43, no. 2, pp. 426-440, March 1997; J. Jang, K. B. Lee, and Y.-H. Lee, “Frequency-time domain transmit power adaptation for a multi-carrier network in fading channels,” Electron. Lett., vol. 38, no. 5, pp. 218-220, February 2002; B. Krongold, K. Ramchandran, and D. Jones, “Computationally efficient optimal power allocation algorithms for multi-carrier communication networks,” IEEE Trans. Commun., vol. 48, no. 1, pp. 23-27, January 2000; and A. Keke and J. M. Cioffi, “A maximum rate loading algorithm for discrete multitone modulation networks,” in Proc. IEEE GLOBECOM, pp. 1514-1518, November 1997; R. F. H. Fischer and J. B. Huber, “A new loading algorithm for discrete multitone transmission,” in Proc. IEEE GLOBECOM, London, U.K., pp. 724-728, November 1996.
The single-user water-filling algorithm can be extended to a multi-user waterfilling algorithm described by R. S. Cheng and S. Verdú, “Gaussian multiaccess channels with ISI: Capacity region and multi-user water-filling,” IEEE Trans. Inf. Theory, vol. 39, no. 3, pp. 773-785, May 1993. However, that algorithm does not take into account practical issues such as the QoS requirements for individual users.
When considering realistic constraints for multi-user, multi-carrier network, the existing resource allocation algorithms can be categorized into two classes based on the optimization criteria: minimizing power given a QoS constraint, and maximizing throughput given power constraint.
The first class considers the problem of minimization of the overall transmission power given the constraint of QoS requirements of individual users, see C. Y. Wong, R. S. Cheng, K. B. Letaief, and R. D. Murch, “Multi-user OFDM with adaptive subcarrier, bit and power allocation,” IEEE J. Sel. Areas Commun., vol. 17, no. 10, pp. 1747-1758, October 1999; D. Kivanc, G. Li, and H. Liu, “Computationally efficient bandwidth allocation and power control for OFDMA,” IEEE Trans. Wireless Commun., vol. 2, no. 6, pp. 1150-1158, November 2003; S. Pietzyk and G. J. M. Janssen, “Multi-user subcarrier allocation for QoS provision in the OFDMA networks,” in Proc. IEEE VTC—Fall, September 2002, vol. 2, pp. 1077-1081; S. Pfletschinger, G. Munz, and J. Speidel, “Efficient subcarrier allocation for multiple access in OFDM networks,” in Proc. 7th Int. OFDM Workshop, pp. 21-25, September 2002; H. Yin and H. Liu, “An efficient multi-user loading algorithm for OFDM-based broadband wireless networks,” in Proc. IEEE Globecom, 2000, pp. 103-107.
The second class attempts to maximize the overall throughput under the constraint of the transmission-power budget. See W. Rhee and J. M. Cioffi, “Increase in capacity of multi-user OFDM network using dynamic subchannel allocation,” in Proc. IEEE VTC, pp. 1085-1089, 2000; M. Ergen, S. Coleri, and P. Varaiya, “QoS aware adaptive resource allocation techniques for fair scheduling in OFDMA based broadband wireless access networks,” IEEE Trans. Broadcast., vol. 49, no. 4, pp. 362-370, December 2003; J. Jang, K. B. Lee, and Y. H. Lee, “Transmit power and bit allocations for OFDM networks in fading channel,” in Proc. IEEE Globecom, pp. 858-862, December 2003; S. Pfletschinger, G. Munz, and J. Speidel, “An efficient water-filling algorithm for multiple access OFDMA,” in Proc. IEEE Globecom, Taipei, Taiwan, pp. 681-685, November 2002; Z. Shen, J. G. Andrews, and B. L. Evans, “Optimal power allocation in multi-user OFDM networks,” in Proc. IEEE Global Commun. Conf., pp. 337-341, 2003.
However, all the known methods restrict channel allocations to be exclusive in the time domain for individual users, i.e., two users cannot time share one channel. In other words, the resource allocation is only one dimension. The prior art only considers allocating the channels, while omitting the transmission time. The transmission time is also a scarce resource in wireless communication, and should also be allocated efficiently to multiple users.